package org.example.graph_theory;

import java.util.*;

public class word_chain {

    public static int minNum = Integer.MAX_VALUE;
    public static LinkedList<String> way = new LinkedList<>();
    public static void main(String[] args) {
        //单词接龙

        //字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：
        //每一对相邻的单词只差一个字母。
        // 对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
        //sk == endWord
        //给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。
//        String beginWord = "hit";
//        String endWord = "cog";
//        ArrayList<String> wordList = new ArrayList<>();
//        wordList.add("hot");
//        wordList.add("dot");
//        wordList.add("dog");
//        wordList.add("lot");
//        wordList.add("log");
//        wordList.add("cog");

//        String beginWord = "a";
//        String endWord = "c";
//        ArrayList<String> wordList = new ArrayList<>();
//        wordList.add("a");
//        wordList.add("b");
//        wordList.add("c");

//        String beginWord = "hot";
//        String endWord = "dog";
//        ArrayList<String> wordList = new ArrayList<>();
//        wordList.add("hot");
//        wordList.add("dog");
//        wordList.add("dot");

        String beginWord = "ymain";
        String endWord = "oecij";
        ArrayList<String> wordList = new ArrayList<>();
        wordList.add("ymann");
        wordList.add("yycrj");
        wordList.add("oecij");
        wordList.add("ymcnj");
        wordList.add("yzcrj");
        wordList.add("yycij");
        wordList.add("xecij");
        wordList.add("yecij");
        wordList.add("ymanj");
        wordList.add("yzcnj");
        wordList.add("ymain");

        int i = ladderLength(beginWord, endWord, wordList);
        System.out.println(i);
    }


    //bfs改进，91ms
    public static int ladderLength(String beginWord, String endWord, List<String> wordList) {
        HashSet<String> hashSet = new HashSet<>(wordList);
        if (hashSet.size() == 0 || !hashSet.contains(endWord)) return 0;
        LinkedList<String> linkedList = new LinkedList<>();
        linkedList.add(beginWord);
        HashMap<String, Integer> map = new HashMap<>();
        map.put(beginWord,1);

        while(!linkedList.isEmpty()){
            String word = linkedList.removeFirst();
            Integer len = map.get(word);
            for (int i = 0; i < word.length(); i++) {
                char[] chars = word.toCharArray();
                for (char j = 'a'; j <= 'z'; j++) {
                    chars[i] = j;
                    String value = String.valueOf(chars);
                    if (value.equals(endWord)) return len + 1;

                    if (hashSet.contains(value) && !map.containsKey(value)){
                        map.put(value,len+1);
                        linkedList.add(value);
                    }
                }
            }
        }

        return 0;
    }


    //bfs,超时
    public static int ladderLength3(String beginWord, String endWord, List<String> wordList) {
        int len = 1;
        LinkedList<String> linkedList = new LinkedList<>();
        boolean[] visited = new boolean[wordList.size()];
        linkedList.add(beginWord);
        while (!linkedList.isEmpty()){
            int size = linkedList.size();
            while (size > 0){
                String begin = linkedList.removeFirst();
                for (int i = 0; i < wordList.size(); i++) {
                    String s = wordList.get(i);
                    if (!visited[i] && differentNumber(begin,s)){
                        linkedList.add(s);
                        if (s.equals(endWord)){
                            len++;
                            return len;
                        }
                        visited[i] = true;
                    }
                }
                size--;
            }
            len++;
        }
        return 0;
    }

    //暴力dfs,超时
    public static int ladderLength2(String beginWord, String endWord, List<String> wordList) {
        boolean[] visited = new boolean[wordList.size()];
        dfs(beginWord,endWord,wordList,visited);
        return minNum == Integer.MAX_VALUE ? 0 : minNum;
    }

    public static void dfs(String beginWord, String endWord, List<String> wordList,boolean[] visited){
        if (!way.isEmpty() && way.getLast().equals(endWord)){
            minNum = Math.min(minNum,way.size()+1);
        }
        for (int i = 0; i < wordList.size(); i++) {
            String s = wordList.get(i);
            if (!visited[i] && differentNumber(beginWord,s)){
                way.add(s);
                visited[i] = true;
                dfs(s,endWord,wordList,visited);
                visited[i] =  false;
                way.remove(s);
            }
        }
    }

    public static boolean differentNumber(String w1,String w2){
        int dp[][] = new int[w1.length()+1][w2.length()+1];
        for (int i = 1; i < w1.length()+1; i++) {
            dp[i][0] = i;
        }

        for (int i = 1; i < w2.length()+1; i++) {
            dp[0][i] = i;
        }

        for (int i = 1; i < w1.length()+1; i++) {
            for (int j = 1; j < w2.length() + 1; j++) {
                if (w1.charAt(i-1) == w2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1];
                }else {
                    dp[i][j] = Math.min(dp[i-1][j],Math.min(dp[i-1][j-1],dp[i][j-1]))+1;
                }
            }
        }

        return dp[w1.length()][w2.length()] == 1;
    }
}